`
https://leetcode.cn/problems/unique-paths-iii/
`

/**
 * @param {number[][]} grid
 * @return {number}
 */
var uniquePathsIII = function (grid) {
  let res = 0
  const m = grid.length, n = grid[0].length
  const visited = new Array(m).fill(null).map(() => new Array(n).fill(false))
  // 起点
  let startI = 0, startJ = 0
  // 一共需要走多少方格
  let totalCount = 0
  // 当前已经走了多少方格
  let visitedCount = 0

  // 找出起点和所有需要走的方格的数量
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        startI = i
        startJ = j
      }
      if (grid[i][j] === 0 || grid[i][j] === 1) {
        totalCount++
      }
    }
  }

  const traverse = (i, j) => {
    // 边界
    if (i < 0 || j < 0 || i >= m || j >= n) {
      return
    }

    // 已经走过或遇到障碍
    if (visited[i][j] || grid[i][j] === -1) {
      return
    }

    // 走到终点且全部走完
    if (grid[i][j] === 2) {
      if (totalCount === visitedCount) {
        res++
      }
      return
    }

    visited[i][j] = true
    visitedCount++

    traverse(i + 1, j)
    traverse(i - 1, j)
    traverse(i, j + 1)
    traverse(i, j - 1)

    visitedCount--
    visited[i][j] = false
  }

  traverse(startI, startJ)

  return res
};